from random import randint

test_list = [randint(1, 1000) for i in range(1000000)]
print(test_list)

def merge_sort(test:list):
    """
    利用递归对数组进行切分，然后merge成为有序列表.
    :param test:
    :return:
    """
    # print(test)
    if len(test)<=1:
        return  test
    mid=len(test)//2
    left=merge_sort(test[0:mid])
    right=merge_sort(test[mid:len(test)])
    leftIndex=rightIndex=0
    helperList=[]
    while leftIndex<=len(left)-1 and rightIndex<=len(right)-1:
       if left[leftIndex]<right[rightIndex]:
           helperList.append(left[leftIndex])
           leftIndex+=1
       else:
           helperList.append(right[rightIndex])
           rightIndex+=1
    helperList.extend(left[leftIndex:])
    helperList.extend(right[rightIndex:])
    return  helperList
# 2 7  9| 5 8 10
# 2 5  9| 7 8 10
print(merge_sort(test_list))